Cây biểu diễn biểu thức Kí pháp Ba Lan

Dùng cây biểu diễn biểu thức có thể thấy rõ trình tự tính toán biểu thức.

Ví dụ:

a * (b + c) - d ^ 5

Được thực hiện theo sơ đồ biểu diễn bởi cây nhi phân sau

-  /  \  * ^/ \  / \a + d 5 / \ b c

Ta mô tả quá trình đọc, ghi nhận giá trị và thực hiện phép tính, giống như quá trình duyệt cây biểu thức theo thứ tự giữa như sau:

  1. Đọc và ghi nhận giá trị biến a (con trái)
  2. Đọc và ghi nhận loại phép toán * (con trái)
  3. Đọc giá trị biến b (con trái)
  4. Đọc và ghi nhận loại phép toán + (con phải)
  5. Đọc giá trị biến c (con phải) thực hiện phép cộng b + c = x và ghi nhận kết quả x, thực hiện phép nhân a * x = y và ghi nhận kết quả y
  6. Đọc và ghi nhận phép toán -
  7. Đọc giá trị biến d
  8. Đọc và ghi nhận phép toán ^
  9. Đọc giá trị 5 và thực hiện phép lũy thừa z = d ^ 5, thực hiện phép trừ k = y - z

Để đơn giản ta giả sử các phép toán đều là hai ngôi. Khi đó cây biểu thức là cây nhị phân đầy đủ. Quy tắc thực hiện phép toán trên cây như sau:

  • Hoặc duyệt cây theo thứ tự giữa mỗi lần duyệt con phải nếu đã tính được giá trị tại con đó thì thực hiện phép tính quy định bởi toán tử ghi tại đỉnh cha.
Viết tuần tự các đỉnh duyệt theo thứ tự giữa thì ta có dãy
 -   - / \   / \  *  ^  +  ^ / \ / \ / \ / \a + d 5  * c d  5  / \  / \ b c  a b
a * b + c - 4 * d ^ 5 (1)

Theo cách này, mỗi khi duyệt một đỉnh

  1. Nếu là lá bên trái (biến hoặc hằng) thì ghi nhận giá trị của biến
  2. Nếu là toán tử thì lưu dạng của toán tử
  3. Nếu là con phải và lá thực hiện phép tính theo toán tử đã lưu ở đỉnh cha giữa các giá trị đã lưu tại con phải và giá trị mới đọc tại con trái, ghi kết quả vào đỉnh cha.
  • Hoặc duyệt cây biểu thức trên theo thứ tự sau: Mỗi đỉnh được duyệt sau khi cả hai đỉnh con đã được duyệt. Khi đó mỗi khi duyệt một đỉnh trong ta thực hiện toán tử ghi tại đỉnh này với giá trị của hai con của đỉnh ấy.
Thứ tự duyệt các đỉnh khi đó sẽ là:a b c + * d 5 ^ - (2)

Khi duyệt theo thứ tự sau, việc thực hiện phép tính tiến hành theo quy tắc:

Mỗi khi thăm một đỉnh thì:

  1. Nếu là lá thì ghi nhận giá trị của biến
  2. Nếu là đỉnh trong thì thực hiện toán tử ghi ở đỉnh này vào các giá trị ghi ở hai đỉnh con, ghi kết quả vào chính đỉnh này.

Với dãy (1) nếu không dùng đến dấu ngoặc, có thể có hai cây biểu thức khác nhau cho cùng một dãy đỉnh khi duyệt thứ tự giữa. Còn với dãy (2) cùng với lưu ý rằng các biến và hằng luôn được biểu diễn bằng các lá, các toán tử luôn biểu diễn bởi các nút trong, từ mỗi dãy dạng (2) ta luôn dựng lại được cây biểu thức duy nhất theo giải thuật sau:Khi độ dài dãy lớn hơn 1, duyệt từ bên trái sang, nếu gặp một phần tử là toán tử, thì lấy hai phần tử đứng trước nó ra khỏi dãy chuyển thành hai con của phần tử ấy (theo đúng thứ tự).Vì thế biểu thức viết bởi dãy (2) là hoàn toàn xác định.